//
//  Problem34.swift
//  TestProject 34. 在排序数组中查找元素的第一个和最后一个位置
//
//  Created by 武侠 on 2020/8/21.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 34. 在排序数组中查找元素的第一个和最后一个位置
 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 你的算法时间复杂度必须是 O(log n) 级别。
 如果数组中不存在目标值，返回 [-1, -1]。

 示例 1:
 输入: nums = [5,7,7,8,8,10], target = 8
 输出: [3,4]
 
 示例 2:
 输入: nums = [5,7,7,8,8,10], target = 6
 输出: [-1,-1]
 */
@objcMembers class Problem34: NSObject {
    func solution() {
        let list = [5,6,7,7,8,8,10]
        
        print(list)
        for item in list {
            print("item = ", item)
            print(searchRange(list, item))
        }
        
        print(searchRange(list, 11))
        print(searchRange(list, 9))
    }
    
    // 思路：
    // 1: 先根据二分法，找到target
    // 2: 然后 前后2个数组，找刚刚比target小的值，和刚刚比target大的值
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        if nums.count == 0 {
            return [-1, -1]
        }
        if nums.count == 1 {
            return nums[0] == target ? [0, 0] : [-1, -1]
        }
        
        var l = 0                       // Left
        var r = nums.count - 1          // Right
        var st = -1
        
        if nums[0] == target {
            let right = searchMaxValue(nums, target, 0, nums.count - 1)
            return [0, right]
        } else if nums[nums.count-1] == target {
            let left = searchMinValue(nums, target, 0, nums.count - 1)
            return [left, nums.count - 1]
        } else {
            while l <= r {
                let mid = (l + r) / 2       // Mid
                if nums[mid] == target {            // 找到
                    st = mid
                    break
                } else if nums[mid] < target {      // 小于
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
            
            if st == -1 {
                return [-1, -1]
            }
            
            let left = searchMinValue(nums, target, 0, st)
            let right = searchMaxValue(nums, target, st, nums.count - 1)
            
            return left > right ? [-1, -1] : [left, right]
        }
    }
    
    func searchMinValue(_ nums: [Int], _ target: Int, _ l: Int, _ r: Int) -> Int {
        var left = l
        var right = r
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] == target {
                right = mid - 1
            } else if nums[mid] < target {
                left = mid + 1
            }
        }
        return left
    }
    
    func searchMaxValue(_ nums: [Int], _ target: Int, _ l: Int, _ r: Int) -> Int {
        var left = l
        var right = r
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] == target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid - 1
            }
        }
        return right
    }
}
